1. Field of the Invention
The present invention relates to a system for monitoring a flow of packets in a network, and particularly relates to a system for monitoring a flow of cells of an ABR communication in an ATM network.
2. Description of the Related Arts
In recent years, a service handling various types of communications, including image data which requires a higher transmission speed, in addition to voice data, text data, etc., has become more and more essential. The core technique of such a service is an ATM (Asynchronous Transfer Mode) method.
The ATM method takes advantage of a cell where control information called a header is added to its payload, divided into a fixed length of 48 octets, as a data transmission unit (data exchange unit).
Currently, discussions about an ABR (Available Bit Rate) service class are frequently made as a method for applying the ATM technique to a high-speed data communication network such as a LAN, a WAN, etc. In the ABR service class, congestion control is performed between a network and a terminal for each connection.
A CBR (Constant Bit Rate) service which allocates a fixed transmission band for each connection, monitors a maximum request band PCR, while a VBR (Variable Bit Rate) service which dynamically allocates a transmission band for each connection according to band information managed by a CAC (Call Admission Control), monitors the maximum request band PCR and an average request band SCR (Sustainable Cell Rate), in order to perform a congestion control using respective results of monitoring the above described bands.
For the ABR communication, a minimum available band MCR (Minimum Cell Rate) and the maximum request band PCR (Peak Cell Rate), are set by a negotiation between a user and a network, when a call is established. These settings are made by the CAC for each connection.
Also for the ABR communication, a data transmitting terminal transmits a cell called an RM (Resource Management) cell for each predetermined number of transmission data cells. The network or a receiving terminal writes control information indicating whether or not resource information or congestion occurs in the network, etc., to the RM cell, and returns that RM cell to the transmitting terminal. When receiving the RM cell to which the control information, etc. is written, the transmitting terminal calculates a transmission allowed band ACR (Allowed Cell Rate) according to the control information. The ACR is a cell rate at which the transmitting terminal is allowed to perform a transmission to a network (cell transfer speed). This cell rate varies between the minimum available band MCR and the maximum request band PCR. The transmitting terminal transmits a cell at a transfer rate within an allowable range of the ACR transfer rate. Thus, for the ABR communication, a cell rate at which a transmitting terminal is allowed to perform a transmission to a network is determined depending on a use state of a network by using feedback control.
If a network is not in congestion state, a transmitting terminal can transmit a cell in the maximum request band PCR. If the network is in congestion state, the transmitting terminal recognizes the congestion state by an RM cell fed back from the network, and progressively reduces a size of an ACR. The minimum value of the ACR is an MCR. Assume that the ACR at a certain transmitting terminal is the MCR. If the transmitting terminal transmits a cell at a transmission rate equal to or higher than the MCR (that is, if the transmitting terminal transmits the cell beyond the transmission-allowable range), the congestion state continues. This is because a large amount of cells flow into the network even though the network is in the congestion state. Even if the network is in a normal state (not in congestion state), the network may often enter a congestion state when the transmitting terminal transmits a cell at a transmission rate equal to or higher than the PCR or the ACR.
To prevent a network from entering congestion state, a process such as monitoring a flow of cells (an amount of data) at an entry point of the network, discarding a cell which violates a predetermined transmission rate (a PCR or an MCR), etc. must be performed. As a method for monitoring the flow of cells, a method for making a comparison between an actual flow of cells and a predetermined transmission rate (a PCR or an MCR) can be considered.
As described above, for the ATM technique which is the basic technique of a B-ISDN (Broadband-Integrated Service Digital Network), a usage parameter control technique (or a polcing technique) for controlling a flow of cells by determining whether or not a flow of user cells from a user terminal into an ATM network exceeds a value set by a user, becomes essential.
With the usage parameter control technique UPC, a flow of user cells is measured for each connection such as a virtual path (VP), a virtual channel (VC), etc., and a comparison between the flow of user cells and an amount of flow set by the user is made. As a result of the comparison, a violation cell is discarded or tagged (attached with a violation tag). As such a congestion control method in an ATM network, the above described ABR (Available Bit Rate) method is known.
A service implemented by the ABR method monitors a congestion caused by a concentration of traffic. If a congestion occurs, the transmission rate at a transmitting terminal must be lowered. To lower the transmission rate, it is currently being discussed to notify the transmitting terminal of a currently allowable transmission rate or a currently occurring congestion, so that the transmitting terminal which receives the notification can voluntarily lower its transmission rate.
With the service implemented by the ABR method, a user terminal reports a minimum cell rate (MCR), a peak cell rate (PCR), etc., when establishing a call, and transmits data based on these parameters. A network instructs the user terminal to vary an ACR (Allowed Cell Rate) according to its congestion state, depending on need. The usage parameter control UPC implemented by the ABR method performs a usage parameter control for the varying ACR.
FIG. 1 is a schematic showing an ATM network.
The ATM network is configured by, for example, interconnecting an arbitrary number of ATM switches (SWs), and arranging a virtual path VP and a virtual channel VC between a transmitting terminal and a receiving terminal as shown in FIG. 1, in order to transmit an ATM cell. In this case, a usage parameter control unit UPC monitoring if a user transmits cells as set is positioned at an entry point of the ATM network.
The usage parameter control UPC determines whether or not an arrived cell is a violation cell. If the arrived cell is determined to be a violation cell, it is discarded or tagged. The leaky bucket algorithm, for example, is recommended as a standard algorithm by the ITU-T, etc. The virtual scheduling algorithm equivalent to the leaky bucket algorithm is also well-known.
FIGS. 2A and 2B are schematics showing a notification process of a congestion. 21 indicates a user transmitting terminal. 22 indicates a user receiving terminal. 23 and 24 indicate switches such as an ATM switch (SW1 and SW2). The ATM network is configured by these switches 23 and 24. FIG. 2A is a schematic diagram showing a congestion notification method implemented by a forward notification, while FIG. 2B is a schematic diagram showing a congestion notification method implemented by a backward notification.
User cells are transmitted from the user terminal 21, and an RM cell is inserted as a control cell for each predetermined number of user cells. When it receives the RM cell, the receiving terminal 22 returns the RM cell. In this case, the RM cell transmitted from the transmitting terminal 21 to the receiving terminal 22 is called an F-RM (Forward RM) cell, while the RM cell transmitted from the receiving terminal 22 to the transmitting terminal 21 is called a B-RM (Backward RM) cell.
FIG. 3 shows a format of a resource management cell (RM cell) which performs a congestion notification, a transmission rate notification, etc. A5-byte header is composed of a GFC which is a 4-bit controller for performing a general flow control, a VPI which is an 8- or 12-bit virtual path identifier, a VCI which is a 16-bit virtual channel identifier, a PT which indicates a 3-bit payload type, a CLP which displays a 1-bit cell loss priority, and a CRC which is an 8-bit controller for performing a header error control. For the PT, for example, a bit pattern "000" indicates a user cell in a non-congestion state, and a bit pattern "110" indicates a resource management cell.
A 48-byte payload of the resource management cell is composed of a 1-byte resource management protocol identifier "RM Protocol ID", another one byte including fields such as a 1-bit DIR (Direction) field, a 1-bit BN (Backward Explicit Congestion Notification) field, a 1-bit CI (Congestion Indication) field, a 1-bit NI (No Increase: invariable cell) field, a 1-bit RA (Request/Acknowledge) field, and 3-bits of unused fields (Res), a 2-byte ER (Explicit Cell Rate) field, a 2-byte CCR (Current Cell Rate) field, a 2-byte MCR (Minimum Cell Rate) field, a 4-byte QL (Queue Length) field, a 4-byte SN (Sequence Number) field, 30-bytes and 6-bits of unused fields (Res), and 10-bit CRC (Cyclic Redundancy Check) fields.
The GFC/VPI included in the header is used as a flow control GFC for a user network interface (UNI), while it is used as part of a virtual path identifier VPI for a network node interface (NNI). Accordingly, the virtual path identifier VPI is 8 bits for the UNI, while it is 12 bits for the NNI.
The DIR (Direction) is a direction instructing bit. The value "0" indicates an F-RM cell, and the value "1" indicates a B-RM cell. The BN is a backward congestion notification bit indicating a B-RM cell generated in a switch (SW) in an ATM network or in a receiving terminal. The CI is a congestion indication bit, the NI is an invariable cell rate bit, and the RA is a request/acknowledgement bit not used in an ABR service.
The ER is a 2-byte allowed cell rate, the CCR is a 2-byte current cell rate, the QL is a 4-byte queue length not used in the ABR service, and the SN is a 4 byte sequence number. The resource management cell also includes 30-bytes and 6-bits of unused fields (Res), and a 10-bit CRC (Cyclic Redundancy) field at the end of the format.
The RM cell configured as above is transmitted from a transmitting terminal to a receiving terminal via a plurality of switches (SWs). When a congestion occurs in an ATM network, the EFCI (Explicit Forward Congestion Indication) bit in the user cell passing through the congested SW may be set, or an allowed cell rate in the plurality of switches (SWs) may be written to an ER field of the RM cell. The receiving terminal which receives a RM cell returns that cell to the transmitting terminal. When receiving terminal turns a RM cells, the receiving terminal set a congestion indication flag in the RM cell if the previous user cell's EFCI is set. The receiving terminal which receives such an RM cell returns that cell. The transmitting terminal determines whether or not a congestion occurs according to the returned RM cell, and controls a cell transmission rate according to a result of the determination. That is, in the above described ABR service, the transmitting terminal controls the transmission rate depending on a state of the ATM network.
In the ATM network, a usage parameter control unit UPC is used for monitoring if cells are transmitted as set by a user as described above, and the cells are monitored using, for example, the leaky bucket algorithm.
When transmitting an F-RM cell, the transmitting terminal sets a peak cell rate PCR set by the user in an allowed cell rate field ER of the F-RM cell when a call is established. Additionally, the transmitting terminal sets an allowed cell rate ACR in a current cell rate field CCR, and sets the minimum cell rate in a minimum cell rate field MCR. When receiving a B-RM cell, the transmitting terminal can raise a cell rate within an allowable range of the PCR according to a predetermined rule if a congestion indication bit CI does not indicate an occurrence of a congestion, and if a no increase bit NI indicates that the cell rate can be raised. If the congestion indication bit CI indicates the occurrence of the congestion, the cell rate must be dropped in a range not lower than the MCR according to a predetermined rule.
With the congestion notification method implemented by a forward notification shown in FIG. 2A, an explicit forward congestion indication (EFCI) bit of a cell transmitted to a receiving terminal 22 is set to "1", when a congestion marked with an asterisk occurs in a switch 23. The receiving terminal 22 terminates a user cell, and returns an F-RM cell as a B-RM cell whose congestion indication bit CI is set to "1" by the receiving terminal, to the transmitting terminal 21. When receiving the B-RM cell where the congestion indication bit CI is set to "1" indicating an occurrence of a congestion, the transmitting terminal 21 lowers the transmission cell rate, thereby avoiding the congestion in the switch 23.
In the meantime, with the congestion notification method implemented by a backward notification shown in FIG. 2B, the congestion indication bit CI of the B-RM cell is set to "1" in the switch 23 and transmitted, when the congestion marked with the asterisk occurs in the switch 23 in a similar manner as in the above described case. When receiving the B-RM cell whose congestion indication bit CI is set to "1", the transmitting terminal 21 determines the occurrence of the congestion and lowers the cell transmission rate. Otherwise, the transmitting terminal 21 may make the cell transmission rate equal to or lower than the allowed cell rate ER of the B-RM cell.
FIG. 4 is a block diagram showing a conventional usage parameter control device: 41 indicates a cell information separation unit; 42 indicates a cell delay unit; 43 indicates a cell control unit; 44 indicates a flow measurement unit; 45 indicates a parameter storage unit; and 46 indicates a B-RM cell detection unit. In a similar manner as in a fixed bit rate CBR service and a variable bit rate VBR service, a B-RM cell detection unit 46 is removed from the above described configuration when performing a cell flow control according to a value set by a user. The value set by the user is stored in the parameter storage unit 45. A VPI and a VCI included in a header of a user cell separated by the cell information separation unit 41 are identified to measure flows of user cells for each VPI and VCI. Each of the measured flows is compared with the value set by the user stored in the parameter storage unit 45. As a result of the comparison, user cells of the flows exceeding the value set by the user are discarded or tagged in the cell control unit 43. The cell delay unit 42 is intended to supply cells for the cell control unit 43 to compensate for any delay in a process caused by the flow measurement unit, etc.
Additionally, in the ABR service, the B-RM cell detection unit 46 detects a B-RM cell transmitted from the receiving terminal. If the CI bit of the detected B-RM cell is set to "1", it indicates an occurrence of a congestion. Therefore, to avoid the congestion, the flow of user cells is controlled by changing a parameter for a usage parameter control, stored in the parameter storage unit 45. The transmitting terminal which receives this B-RM cell lowers the cell transmission rate.
FIG. 5 is a schematic diagram showing a process of a conventional delay control. Between a transmitting terminal 51 and an interface 52 in a switch (ATM switch), a time "Tsi" is required from a transmission of the above described B-RM cell from the interface 52 till an arrival of the cell, transmitted at a rate changed by the transmitting terminal 51 which receives that B-RM cell on a route indicated by the dotted line.
Accordingly, a parameter of the usage parameter control in the interface 52 in the switch is normally changed after the time "Tsi" elapses from the transmission of the B-RM cell. It is impossible, however, to fix the time "Tsi". This is because a processing time of the B-RM cell in the transmitting terminal 51 and a distance from the transmitting terminal to the interface 52 may vary and fluctuate.
As a result, the maximum value .tau.2 and the minimum value .tau.3 of the time Tsi are set in the interface 52 as delay standard values. Assuming that a B-RM cell passes through the interface 52 at a time t0, a duration from the time t0 till a time t2 is the minimum value .tau.3, and a duration from the time t0 till a time t3 is the maximum value .tau.2. If the time is divided into three, i.e., the duration A from time t0 to time t2, the duration B from time t2 to time t3, and the duration C from time t3, the relationship between .tau.3, Tsi, and .tau.2 is therefore .tau.3.ltoreq.Tsi.ltoreq..tau.2.
Since user cells in the duration A are not affected by the B-RM cell, there is no need to change the parameters.
In the next duration B, it cannot be determined whether or not user cells in the duration B are affected by the B-RM cell. Therefore, when a cell rate is lowered according to a congestion indication such as CI=1, etc., the parameters are not changed as shown in (a). When the congestion is resolved and the value of the CI is changed from 1 to 0, the parameters must be changed so that the cell rate can be raised as shown in (b). This is because raising the cell rate is a control which does not discard the user cells. In the duration C, since all of user cells are affected by the B-RM cell, the parameters are changed even when the cell rate is lowered as shown in (a).
FIG. 5 also shows the case where a B-RM cell of another connection passes at the time t1, and the maximum value of this VP/VC is set to .tau.2'. That is, the maximum and minimum values of the time Tsi can be set for each VP/VC.
As described above, to perform the usage parameter control by setting the maximum value .tau.2 and the minimum value .tau.3 for the time Tsi, a configuration as shown in FIG. 6 may be adopted. In this figure, 61 indicates a cell information separation unit, 62 indicates a cell delay unit, 63 indicates a cell control unit, 64 indicates a flow measurement unit, 65 indicates a parameter storage unit, 66 indicates a B-RM cell detection unit, 67 indicates a delay control unit, in which 68 indicates a counter for measuring a duration of the maximum value .tau.2, 69 indicates a counter for measuring a duration of the minimum value .tau.3, and CLK indicates a clock signal.
When B-RM cell detection unit 66 detects a B-RM cell, the counters 68 and 69 start counting the clock signal CLK. Assuming that the B-RM cell passes the time t0 in FIG. 5 and the counters 68 and 69 start counting, the counter 69 feeds a minimum value elapsed time signal to the parameter storage unit 65 at the time t2. Since the value of the counter 68 reaches the maximum value .tau.2 at the time t3, the counter 68 feeds a maximum value elapsed time signal to the parameter storage unit 65.
In this case, to lower the cell rate due to an occurrence of a congestion, parameters are changed according to the maximum value elapsed time signal. To raise the cell rate due to clearing of the congestion, the parameters are changed according to the minimum value elapsed time signal.
FIG. 7 is a block diagram showing details of a conventional usage parameter control device UPC, which is slightly different from the above described configuration of FIG. 4.
The correspondence between the configuration of FIG. 7 and that of FIG. 4 is as follows. 71 indicates a header extraction unit corresponding to the cell information separation unit 41. 72 indicates a delay unit corresponding to the cell delay unit 42. 73 indicates a control unit corresponding to the cell control unit 43. An operation unit indicated by 74 and an operation memory indicated by 76 correspond to the flow measurement unit 44. A parameter table indicated by 75 corresponds to the parameter storage unit 45. In the parameter table 75, a value tt indicates a violation threshold value, and T0 indicates a minimum cell interval. A value LT indicates an arrival time of a preceding cell, and CM indicates a leaky bucket counter in the memory 76. The violation threshold value tt and the minimum cell interval T0 are set, updated, etc. by a computer not shown in the drawing, etc. via a computer interface COM-IF. The parameter table 75 and the operation memory 76 are formed for each virtual path VP or each virtual channel VC. The parameter table 75 and the operation memory 76 are accessed using a virtual path identifier VPI or a virtual channel identifier VCI of a header extracted by the header extraction unit 71, as an address.
FIG. 8 is a flowchart showing the leaky bucket algorithm. If a cell arrives at a time Ta (step (a)), a leaky bucket counter CM arranged in the operation memory 76 is updated to CM=CM-(Ta-LT) (step (b)), based on the assumption that an arrival time of a preceding cell is LT.
Then, it is determined whether or not the contents of the leaky bucket counter CM is smaller than 0 (step (c)). If it is smaller than 0, it indicates a case where a return rate is made lower and a cell arrives later than an expected arrival time of the cell. Therefore, the CM is set to 0 (step (d)), and the process goes to step (e). If it is not smaller than "0", it is further determined whether or not the value of the leaky bucket counter CM is greater than the violation threshold value tt set in the parameter table 75 (step (e)). If it is greater than the violation threshold value tt, the transmission rate is made higher, and violation cells whose number increases, which arrive at an interval shorter than the minimum cell interval T0, are discarded (step (f)). If it is not greater than the violation threshold value tt, the arrival time of the preceding cell LT is defined as the cell arrival time Ta, and the value of the leaky bucket counter CM is updated to a value obtained by adding the minimum cell interval T0 to the current value of the leaky bucket counter CM (step (g)).
As described above, the operation unit 74 references the violation threshold value tt and the minimum cell interval T0 set in the parameter table 75 corresponding to each virtual path identifier VPI or each virtual channel identifier VCI of a header extracted by the header extraction unit 71, and discards an arrived cell by controlling the control unit 73 when determining a cell as being a violation cell, while updating the arrival time of the preceding cell LT and the value of the leaky bucket counter CM. The delay unit 72 is intended to feed the above described time corresponding to the process time to the arrival cell.
As described above, for the ABR communication, a PCR, an MCR, and an ACR are defined as parameters associated with a transmission rate. The specification of the ABR communication, however, is currently still being discussed, and congestion control in consideration of these three parameters has not yet been performed.
In the ABR communication, the ACR varies depending on a state of a network. Accordingly, to monitor a flow of cells using the ACR, a monitor parameter set in a UPC must be dynamically changed. If a conventional method is simply applied to the ABR communication, and the process of discarding a cell exceeding the minimum available band MCR is performed, the following problem may arise. That is, if the network is in a congestion state and the ACR of a terminal drops to the MCR, discarding the cell exceeding the MCR is an appropriate process. However, if all of cells exceeding the MCR are discarded in a state where the network is not in the congestion state and the ACR of the terminal is greater than the MCR, even cells in an allowed transmission band are discarded.
Accordingly, in the ABR communication, the monitor parameter must be dynamically changed according to the ACR which varies depending on a state of the network. Such a method, however, has not been offered up to now.
Also in a device which dynamically changes a monitor parameter (usage parameter), a B-RM cell exists for each VP/VC. Accordingly, for the above described delay control process, the counter 68 whose maximum value is .tau.2, and the counter 69 whose minimum value is .tau.3, which start counting the clock signal CLK by detecting the B-RM cell, must be arranged for each VP/VC. As a result, the scale of the delay control unit becomes huge.
Furthermore, as shown in FIG. 5, the case may arise where the maximum values of a plurality of connections are different values .tau.2, and .tau.2', and the passage times of the B-RM cells corresponding to the plurality of connections are different, so that the times when the parameters are changed are the same, such as at the time t3. Also the minimum value .tau.3 may vary depending on each connection. If there is a difference between the passage times of the B-RM cells for the plurality of connections, there will be a strong possibility that the parameters must be changed at the same time. Thus, when the parameters are changed simultaneously, a conflict of parameter change requests may occur. As a result, a usage parameter control cannot be performed stably.
The parameter used for the usage parameter control is composed of ten-odd bytes, including an allowed cell rate, etc. To change such a parameter, it must be rewritten immediately. To perform this change operation, a high-speed storage device or a storage device equipped with a wide bus may be adopted. However, implementation using these devices is impossible considering the cost and scale of the circuits, etc.
Additionally, the usage parameter control unit UPC, which is positioned at a transmitting terminal side in an ATM network, determines whether or not a pell transmitted by the transmitting terminal is a violation cell. The violation threshold value tt, the minimum cell interval T0, etc. in the parameter table 75 are set via a computer interface COM-IF. For the ABR service, a cell rate can be raised if a congestion does not occur, while the cell rate is lowered if the congestion occurs, thereby effectively using the ATM network. To cope with such a varying cell rate, a traffic parameter must be dynamically changed for a determination of whether or not the cell is a violation cell. With the conventional usage parameter control unit, however, the traffic parameter cannot be dynamically changed. This is because the traffic parameter is set and updated by a computer via the computer interface COM-IF.